1658A - Marin and Photoshoot - CodeForces Solution

 
import atexit, io, sys, math, heapq, collections

def get_int(): return int(sys.stdin.readline().strip())
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

def write_int(a): sys.stdout.write(str(a)+"\n")
def write_str(a): sys.stdout.write(a+"\n")
def write_list(arr): sys.stdout.write(" ".join(map(str, arr)) + "\n")

def swap(arr, a, b):
    arr[a]^=arr[b]
    arr[b]^=arr[a]
    arr[a]^=arr[b]

def int_len(a): return math.floor(math.log(a,10))+1

def isPowerOfTwo(x): return x and (not(x & (x-1)))

def Sieve(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    res = []
    for i in range(2,len(prime)):
        if (prime[i]):
            res.append(i)
    return res

def binarySearch (arr, l, r, x):
    if r >= l:
  
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        else:
            return binarySearch(arr, mid + 1, r, x)
    else:
        return -1
def search(arr,x): return binarySearch(arr,0,len(arr)-1,x)

def toString(A): return''.join(A)

def toArray(str): return str.split()

def arrSum(Arr):
    Sum =0
    for i in range (len(Arr)):
        Sum+=Arr[i]
    return Sum

def computeXOR(n) :
 
             
        if n % 4 == 0 :
        return n
 
        if n % 4 == 1 :
        return 1
 
        if n % 4 == 2 :
        return n + 1
 
        return 0
 

def find_gcd(x, y):
     
    while(y):
        x, y = y, x % y
     
    return x
         
def isSubSequence(string1, string2, m, n):
        if m == 0:
        return True
    if n == 0:
        return False
 
            if string1[m-1] == string2[n-1]:
        return isSubSequence(string1, string2, m-1, n-1)
 
        return isSubSequence(string1, string2, m, n-1)

def sum(a,b):
    if (b.find('-')!=-1):
        return "-1"
    L1= len(a)
    L2= len(b)
    res =""
    if (L1<L2):
        a='0'*(L2-L1)+a
    elif (L2<L1):
        b='0'*(L1-L2)+b
    for i in range(0,max(L1,L2)):
        s=a[i]
        t=b[i]
        p=int(a[i])+int(b[i])
        res+=str(p)
    return res

def isPalin(s):
    return s == s[::-1]

    
def nextPermutation( nums):
    i=len(nums)-1
    flag=True
    while (i>=1):
        if nums[i]>nums[i-1]:
            i-=1
            flag=False
            break
        i-=1

    if i==0 and flag:
        nums.reverse()
    else:
        diff=10000000
        index=i
        j=i
        while(j<len(nums)):
            if (nums[j]>nums[i] and diff>=nums[j]-nums[i]):
                index=j
                diff=nums[j]-nums[i]
            j+=1
        temp=nums[index]
        nums[index]=nums[i]
        nums[i]=temp
        nums[i+1:]=reversed(nums[i+1:])   
    return nums

def pairs(arr, size, n):
 
    mpp = {}
 
    for i in range(size):
        if arr[i] in mpp.keys():
             mpp[arr[i]] += 1
        else:
             mpp[arr[i]] = 1
 
    for i in range(size):
         if n + arr[i] in mpp.keys():
                        return True
     
        return False


    
N= get_int()
while N>0:
    n = get_int()
    S= get_string()
    res = 0
    i=0
    while i<len(S):
        if S[i]=='0':
            j=i+1
            while j<len(S):
                if S[j]=='0':
                    if j-i==1:
                        res+=2
                    elif j-i==2:
                        res+=1
                    break
                j+=1
            i=j
            continue
        i+=1
    print(res)

    N-=1